/***************************************************************************************
* Copyright (c) 2014-2022 Zihao Yu, Nanjing University
*
* NEMU is licensed under Mulan PSL v2.
* You can use this software according to the terms and conditions of the Mulan PSL v2.
* You may obtain a copy of Mulan PSL v2 at:
*          http://license.coscl.org.cn/MulanPSL2
*
* THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
* EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
* MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
*
* See the Mulan PSL v2 for more details.
***************************************************************************************/

#include <isa.h>

/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <regex.h>
#include <memory/vaddr.h>

enum {	
    TK_ADD = '+',
    TK_SUB = '-',
    TK_MUL = '*',
    TK_DIV = '/',

    TK_LPAR = '(',
    TK_RPAR = ')',

    TK_NOTYPE = 256, 

    TK_NUM,
    TK_REG,

    TK_EQ,
    TK_NEQ,

    TK_GT,
    TK_LT,

    TK_AND,
    TK_OR,
    TK_NOT,

    TK_DREF, 
    TK_NEG,
};

static struct rule {
    const char *regex;
    int token_type;
} rules[] = {
    {" +", TK_NOTYPE},					// spaces

    {"0[xX][0-9a-fA-F]+", TK_NUM},		// hex number
    {"[0-9]+", TK_NUM},					// dec number
    {"\\$[0-9a-zA-Z]+", TK_REG},		// reg

    {"\\+", TK_ADD},					// plus
    {"-", TK_SUB},						// sub
    {"\\*", TK_MUL},					// mul
    {"/", TK_DIV},						// div

    {"==", TK_EQ},						// equal
    {"!=", TK_NEQ},						// not equal

    {">", TK_GT},						// greater than
    {"<", TK_LT},					    // less than

    {"&&", TK_AND},						// and
    {"\\|\\|", TK_OR},					// or
    {"!", TK_NOT},						// not

    {"\\(", TK_LPAR},					// left bracket
    {"\\)", TK_RPAR},					// right bracket
};

#define NR_REGEX ARRLEN(rules)

static regex_t re[NR_REGEX] = {};

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
    int i;
    char error_msg[128];
    int ret;

    for (i = 0; i < NR_REGEX; i ++) {
        ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
        if (ret != 0) {
            regerror(ret, &re[i], error_msg, 128);
            panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
        }
    }
}

typedef struct token {
    int type;
    char str[32];
} Token;

static Token tokens[64] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;

static bool make_token(char *e) {
    int position = 0;
    int i;
    regmatch_t pmatch;

    nr_token = 0;

    while (e[position] != '\0') {
        /* Try all rules one by one. */
        for (i = 0; i < NR_REGEX; i ++) {
            if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
                char *substr_start = e + position;
                int substr_len = pmatch.rm_eo;

                // Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",
                // 		i, rules[i].regex, position, substr_len, substr_len, substr_start);

                position += substr_len;

                switch (rules[i].token_type) {
                    case TK_NOTYPE:
                        break;
                    case TK_NUM:
                    case TK_REG:
                        sprintf(tokens[nr_token].str, "%.*s", substr_len, substr_start);
                    default:
                        tokens[nr_token].type = rules[i].token_type;
                        ++ nr_token;
                }

                break;
            }
        }

        if (i == NR_REGEX) {
            printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
            return false;
        }
    }

    return true;
}

static int cur_idx;
static word_t parse_expr(bool* success);
static word_t parse_logic_or(bool* success);
static word_t parse_logic_and(bool* success);
static word_t parse_eq_neq(bool* success);
static word_t parse_gt_lt(bool* success);
static word_t parse_add_sub(bool* success);
static word_t parse_mul_div(bool* success);
static word_t parse_unary(bool* success);
static word_t parse_primary(bool* success);


word_t expr(char* e, bool* success) {
    *success = true;
    if (!make_token(e)) {
        *success = false;
        return 0;
    }

    /* TODO: Insert codes to evaluate the expression. */
    cur_idx = 0; // 必须清零!!!
    word_t val = parse_expr(success);
    if (!*success) {
        printf("Invalid expression.\n");
    }
    return val;
}

/**
* expr       := logic_or
* logic_or   := logic_and ("||" and) *
* logic_and  := eq_neq ("&&" eq_neq) *
* eq_neq     := gt_lt ("==" gt_lt | "!=" gt_lt)*
* gt_lt      := add_sub ("<" add_sub | ">" add_sub)*
* add_sub    := mul_div ("+" mul_div | "-" mul_div)*
* mul_div    := unary ("*" unary | "/" unary)*
* unary      := ("+" | "-" | "!" | "*")? primary
* primary    := num | "(" expr ")"
*/
static word_t parse_logic_or(bool* success);
static word_t parse_logic_and(bool* success);
static word_t parse_eq_neq(bool* success);
static word_t parse_gt_lt(bool* success);
static word_t parse_add_sub(bool* success);
static word_t parse_mul_div(bool* success);
static word_t parse_unary(bool* success);
static word_t parse_primary(bool* success);

// expr       := logic_or
static word_t parse_expr(bool* success) {
    return parse_logic_or(success);
}

// logic_or   := logic_and ("||" and) *
static word_t parse_logic_or(bool* success) {
    word_t result = parse_logic_and(success);
    if (!*success) return 0;
    while (cur_idx < nr_token) {
        if (tokens[cur_idx].type != TK_OR) break;
        cur_idx ++;
        word_t right = parse_logic_and(success);
        if (!*success) return 0;
        result = result || right;
    }

    return result;
}

// logic_and  := eq_neq ("&&" eq_neq) *
static word_t parse_logic_and(bool* success) {
    word_t result = parse_eq_neq(success);
    if (!*success) return 0;
    while (cur_idx < nr_token) {
        if (tokens[cur_idx].type != TK_AND) break;
        cur_idx ++;
        word_t right = parse_eq_neq(success);
        if (!*success) return 0;
        result = result && right;
    }

    return result;
}

// eq_neq     := gt_lt ("==" gt_lt | "!=" gt_lt)*
static word_t parse_eq_neq(bool* success) {
    word_t result = parse_gt_lt(success);
    if (!*success) return 0;
    while (cur_idx < nr_token) {
        int type = tokens[cur_idx].type;
        if (type != TK_EQ && type != TK_NEQ) break;
        cur_idx ++;
        word_t right = parse_gt_lt(success);
        if (!*success) return 0;
        if      (type == TK_EQ)     result = result == right;
        else /* (type == TK_NEQ) */ result = result != right;
    }

    return result;
}

// gt_lt      := add_sub ("<" add_sub | ">" add_sub)*
static word_t parse_gt_lt(bool* success) {
    word_t result = parse_add_sub(success);
    if (!*success) return 0;
    while (cur_idx < nr_token) {
        int type = tokens[cur_idx].type;
        if (type != TK_GT && type != TK_LT) break;
        cur_idx ++;
        word_t right = parse_add_sub(success);
        if (!*success) return 0;
        if      (type == TK_GT)    result = result > right;
        else /* (type == TK_LT) */ result = result < right;
    }

    return result;
}

// add_sub    := mul_div ("+" mul_div | "-" mul_div)*
static word_t parse_add_sub(bool* success) {
    word_t result = parse_mul_div(success);
    if (!*success) return 0;
    while (cur_idx < nr_token) {
        int type = tokens[cur_idx].type;
        if (type != TK_ADD && type != TK_SUB) break;
        cur_idx ++;
        word_t right = parse_mul_div(success);
        if (!*success) return 0;
        if      (type == TK_ADD)    result = result + right;
        else /* (type == TK_SUB) */ result = result - right;
    }

    return result;
}

// mul_div    := unary ("*" unary | "/" unary)*
static word_t parse_mul_div(bool* success) {
    word_t result = parse_unary(success);
    if (!*success) return 0;
    while (cur_idx < nr_token) {
        int type = tokens[cur_idx].type;
        if (type != TK_MUL && type != TK_DIV) break;
        cur_idx ++;
        word_t right = parse_unary(success);
        if (!*success) return 0;
        if      (type == TK_MUL)    result = result * right;
        else /* (type == TK_DIV) */ result = result / right;
    }

    return result;
}

// unary      := ("+" | "-" | "!" | "*")? primary
static word_t parse_unary(bool* success) {
    int type = tokens[cur_idx].type;
    if (type == TK_NOT) {
        cur_idx++;
        return !parse_unary(success);
    } 
    if (type == TK_ADD) {
        cur_idx++;
        return parse_unary(success);
    } 
    if (type == TK_SUB) {
        cur_idx++;
        return -parse_unary(success);
    }
    if (type == TK_MUL) {
        cur_idx++;
        return vaddr_read(parse_unary(success), sizeof(word_t));
    } 

    return parse_primary(success);
}

// primary    := num | "(" expr ")"
static word_t parse_primary(bool* success) {
    if (cur_idx >= nr_token) {
        *success = false;
        return 0;
    }

    int type = tokens[cur_idx].type;
    if (type == TK_NUM) {
        return strtoul(tokens[cur_idx++].str, NULL, 0);
    }
    if (type == TK_REG) {
        return isa_reg_str2val(tokens[cur_idx++].str, success);
    }
    if (type == TK_LPAR) {
        cur_idx ++; // 跳过左括号
        word_t result = parse_expr(success);
        if (!*success) return 0;
        if (tokens[cur_idx].type != TK_RPAR) {
            *success = false;
            return 0;
        }
        cur_idx ++; // 跳过右括号
        return result;
    }

    *success = false;
    return 0;
}
